{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Circle and Rectangle Overlapping"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkOverlap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #圆和矩形是否有重叠"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个以 <code>(radius, xCenter, yCenter)</code> 表示的圆和一个与坐标轴平行的矩形 <code>(x1, y1, x2, y2)</code> ，其中 <code>(x1, y1)</code> 是矩形左下角的坐标，而 <code>(x2, y2)</code> 是右上角的坐标。</p>\n",
    "\n",
    "<p>如果圆和矩形有重叠的部分，请你返回 <code>true</code> ，否则返回 <code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>换句话说，请你检测是否 <strong>存在</strong> 点 <code>(x<sub>i</sub>, y<sub>i</sub>)</code> ，它既在圆上也在矩形上（两者都包括点落在边界上的情况）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1 ：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/02/20/sample_4_1728.png\" style=\"width: 258px; height: 167px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>radius = 1, xCenter = 0, yCenter = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>圆和矩形存在公共点 (1,0) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2 ：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>radius = 1, xCenter = 1, yCenter = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3 ：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/02/20/sample_2_1728.png\" style=\"width: 150px; height: 135px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>radius = 1, xCenter = 0, yCenter = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= radius &lt;= 2000</code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= xCenter, yCenter &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= x1 &lt; x2 &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup> &lt;= y1 &lt; y2 &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [circle-and-rectangle-overlapping](https://leetcode.cn/problems/circle-and-rectangle-overlapping/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [circle-and-rectangle-overlapping](https://leetcode.cn/problems/circle-and-rectangle-overlapping/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n0\\n0\\n1\\n-1\\n3\\n1', '1\\n1\\n1\\n1\\n-3\\n2\\n-1', '1\\n0\\n0\\n-1\\n0\\n0\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        ans = 0\n",
    "        if x1 > xCenter or x2 < xCenter:\n",
    "            ans += min((x1 -xCenter) ** 2,(x2 - xCenter) ** 2)\n",
    "        if y1 > yCenter or y2 < yCenter:\n",
    "            ans += min((y1 - yCenter) ** 2, (y2 - yCenter) ** 2)\n",
    "        return ans <= radius ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        dist = 0\n",
    "        if xCenter < x1 or xCenter > x2:\n",
    "            dist += min((x1 - xCenter) ** 2, (x2 - xCenter) ** 2)\n",
    "        if yCenter < y1 or yCenter > y2:\n",
    "            dist += min((y1 - yCenter) ** 2, (y2 - yCenter) ** 2)\n",
    "        return dist <= radius ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        if xCenter<x1:nx = x1\n",
    "        elif xCenter>x2:nx = x2\n",
    "        else: nx = xCenter\n",
    "        if yCenter<y1:ny = y1\n",
    "        elif yCenter>y2:ny = y2\n",
    "        else: ny = yCenter\n",
    "        #正方形上离圆心最近的点是否小于半径\n",
    "        return (nx-xCenter)*(nx-xCenter)+(ny-yCenter)*(ny-yCenter)<=radius*radius        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        xx=[xCenter,x1,x2]\n",
    "        yy=[yCenter,y1,y2]\n",
    "        xx.sort()\n",
    "        yy.sort()\n",
    "        x3=y3=0\n",
    "        if xx[1]!=xCenter:\n",
    "            x3=min(abs(xCenter-x1),abs(xCenter-x2))\n",
    "        if yy[1]!=yCenter:\n",
    "            y3=min(abs(yCenter-y1),abs(yCenter-y2))\n",
    "        if ((y3*y3)+(x3*x3))>(radius*radius):\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        if x1 <= xCenter <= x2 and y1 <= yCenter <= y2:\n",
    "            return True\n",
    "        # 条件 2：圆心位于矩形的上下左右四个区域\n",
    "        elif xCenter > x2 and y1 <= yCenter <= y2:# 右\n",
    "            return radius >= xCenter - x2\n",
    "        elif yCenter < y1 and x1 <= xCenter <= x2:# 下\n",
    "            return radius >= y1 - yCenter\n",
    "        elif xCenter < x1 and y1 <= yCenter <= y2:# 左\n",
    "            return radius >= x1 - xCenter\n",
    "        elif yCenter > y2 and x1 <= xCenter <= x2:# 上\n",
    "            return radius >= yCenter - y2\n",
    "        \n",
    "        else:\n",
    "            return min((x1 - xCenter) ** 2 + (y2 - yCenter) ** 2, (x1 - xCenter) ** 2 + (y1 - yCenter) ** 2, (x2 - xCenter) ** 2 + (y2 - yCenter) ** 2, (x2 - xCenter) ** 2 + (y1 - yCenter) ** 2) <= radius ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        minx = min(abs(x1 - xCenter), abs(x2 - xCenter))\n",
    "        miny = min(abs(y1 - yCenter), abs(y2 - yCenter))\n",
    "        dx = abs((x1 + x2) / 2 - xCenter)\n",
    "        dy = abs((y1 + y2) / 2 - yCenter)\n",
    "        h = (x2 - x1) / 2\n",
    "        v = (y2 - y1) / 2\n",
    "        if (minx ** 2 + miny **2) <= radius ** 2:\n",
    "            return True\n",
    "        elif dx <= radius + h and y1 <= yCenter <= y2:\n",
    "            return True\n",
    "        elif  dy <= radius + v and x1 <= xCenter <= x2:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        def f(i: int, j: int, k: int) -> int:\n",
    "            if i <= k <= j:\n",
    "                return 0\n",
    "            return i - k if k < i else k - j\n",
    "\n",
    "        a = f(x1, x2, xCenter)\n",
    "        b = f(y1, y2, yCenter)\n",
    "        return a * a + b * b <= radius * radius"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        # 我们只需要判断一个简单的东西即可，就是两个中心的连线以及连线上，矩阵的长度是多少，如果矩阵边缘的长度大于 中心距离 - r 代表重叠\n",
    "        dist = 0\n",
    "        if xCenter < x1 or xCenter > x2:\n",
    "            dist += min((x1 - xCenter) ** 2, (x2 - xCenter) ** 2)\n",
    "        if yCenter < y1 or yCenter > y2:\n",
    "            dist += min((y1 - yCenter) ** 2, (y2 - yCenter) ** 2)\n",
    "        return dist <= radius ** 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        #判断圆心是否在矩形里面\n",
    "        if x1<=xCenter<=x2 and y1<=yCenter<=y2:\n",
    "            return True\n",
    "        #判断四个顶点是否在\n",
    "        for x,y in ([x1,y1],[x2,y2],[x1,y2],[x2,y1]):\n",
    "            if math.sqrt((x-xCenter)**2+(y-yCenter)**2)<=radius:\n",
    "                return True\n",
    "        #判断中心点是否和长宽边相交\n",
    "        if x1<xCenter<x2:\n",
    "            if abs(yCenter-y1)<=radius or abs(yCenter-y2)<=radius:\n",
    "                return True\n",
    "        if y1<yCenter<y2:\n",
    "            if abs(xCenter-x1)<=radius or abs(xCenter-x2)<=radius:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        def f(i,j,k):\n",
    "            if i<=k<=j:\n",
    "                return 0\n",
    "            return i-k if k < i else k - j\n",
    "        a = f(x1,x2,xCenter)\n",
    "        b = f(y1,y2,yCenter)\n",
    "        return a**2+b**2 <= radius**2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "            dist = 0\n",
    "            if xCenter < x1 or xCenter > x2:\n",
    "                dist += min((x1 - xCenter) ** 2, (x2 - xCenter) ** 2)\n",
    "            if yCenter < y1 or yCenter > y2:\n",
    "                dist += min((y1 - yCenter) ** 2, (y2 - yCenter) ** 2)\n",
    "            return dist <= radius ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        dist = 0\n",
    "        if xCenter < x1 or xCenter > x2:\n",
    "            dist += min((x1 - xCenter) ** 2, (x2 - xCenter) ** 2)\n",
    "        if yCenter < y1 or yCenter > y2:\n",
    "            dist += min((y1 - yCenter) ** 2, (y2 - yCenter) ** 2)\n",
    "        return dist <= radius ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        dist = 0\n",
    "        if xCenter < x1 or xCenter > x2:\n",
    "            dist += min((x1 - xCenter) ** 2, (x2 - xCenter) ** 2)\n",
    "        if yCenter < y1 or yCenter > y2:\n",
    "            dist += min((y1 - yCenter) ** 2, (y2 - yCenter) ** 2)\n",
    "        return dist <= radius ** 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        #判断圆心是否在矩形里面\n",
    "        if x1<=xCenter<=x2 and y1<=yCenter<=y2:\n",
    "            return True\n",
    "        #判断四个顶点是否在\n",
    "        for x,y in ([x1,y1],[x2,y2],[x1,y2],[x2,y1]):\n",
    "            if math.sqrt((x-xCenter)**2+(y-yCenter)**2)<=radius:\n",
    "                return True\n",
    "        #判断中心点是否和长宽边相交\n",
    "        if x1<xCenter<x2:\n",
    "            if abs(yCenter-y1)<=radius or abs(yCenter-y2)<=radius:\n",
    "                return True\n",
    "        if y1<yCenter<y2:\n",
    "            if abs(xCenter-x1)<=radius or abs(xCenter-x2)<=radius:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        dist = 0\n",
    "        if xCenter < x1 or xCenter > x2:\n",
    "            dist += min( (x1-xCenter)*(x1-xCenter) , (x2-xCenter)*(x2-xCenter))\n",
    "        if yCenter < y1 or yCenter > y2:\n",
    "            dist += min( (y1-yCenter)*(y1-yCenter) , (y2-yCenter)*(y2-yCenter))\n",
    "        return dist <= radius*radius"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        distance = 0\n",
    "        if xCenter<x1 or xCenter>x2:\n",
    "            distance += min((xCenter-x1)**2,(xCenter-x2)**2)\n",
    "        if yCenter<y1 or yCenter>y2:\n",
    "            distance += min((yCenter-y1)**2,(yCenter-y2)**2)\n",
    "        return distance<=radius**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        return xCenter<x1 and (xCenter-x1)**2+(yCenter-max(min(y2, yCenter), y1))**2<=radius**2 or xCenter>x2 and (xCenter-x2)**2+(yCenter-max(min(y2, yCenter), y1))**2<=radius**2 or yCenter<y1 and (yCenter-y1)**2+(xCenter-max(min(x2, xCenter), x1))**2<=radius**2 or yCenter>y2 and (yCenter-y2)**2+(xCenter-max(min(x2, xCenter), x1))**2<=radius**2 or x1<=xCenter<=x2 and y1<=yCenter<=y2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        def get_min(lower,upper,key):\n",
    "            if lower <= key <= upper:\n",
    "                return 0\n",
    "            if key < lower:\n",
    "                return lower - key\n",
    "            if key > upper:\n",
    "                return key - upper\n",
    "        \n",
    "        dist_x = get_min(x1,x2,xCenter)\n",
    "        dist_y = get_min(y1,y2,yCenter)\n",
    "        return dist_x ** 2 + dist_y ** 2 <= radius ** 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, r: int, ox: int, oy: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        return dist((min(max(x1, ox), x2), min(max(y1, oy), y2)), (ox, oy)) <= r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        def xleng(xc,x1,x2):\n",
    "            if xc>=x1 and xc<=x2:\n",
    "                return xc\n",
    "            if xc<x1:\n",
    "                return x1\n",
    "            if xc>x2:\n",
    "                return x2\n",
    "        l=pow(pow(xleng(xCenter,x1,x2)-xCenter,2)+pow(xleng(yCenter,y1,y2)-yCenter,2),0.5)\n",
    "        if l<=radius:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        distance = 0\n",
    "        if xCenter < x1 or xCenter > x2:\n",
    "            distance += min((x1 - xCenter) ** 2, (x2 - xCenter) ** 2)\n",
    "        if yCenter < y1 or yCenter > y2:\n",
    "            distance += min((y1 - yCenter) ** 2, (y2 - yCenter) ** 2)\n",
    "        return distance <= radius ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        # for x in range(x1,x2+1):\n",
    "        #     for y in range(y1,y2+1):\n",
    "        #         if (x-xCenter) ** 2 + (y-yCenter) ** 2 <= radius ** 2:\n",
    "        #             return True\n",
    "        # return False\n",
    "        dx = max(x1 - xCenter, 0, xCenter - x2)\n",
    "        dy = max(y1 - yCenter, 0, yCenter - y2)\n",
    "\n",
    "        # 检查圆心到矩形边界的最短距离是否小于或等于半径\n",
    "        return dx ** 2 + dy ** 2 <= radius ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        distx=float('inf')\n",
    "        disty=float('inf')\n",
    "        for i in range(x1,x2+1):\n",
    "            # if abs(i-xCenter)<distx:\n",
    "            #     xm=i\n",
    "            distx=min(abs(i-xCenter),distx)\n",
    "        for j in range(y1,y2+1):\n",
    "            # if abs(j-yCenter)<disty:\n",
    "            #     ym=j\n",
    "            disty=min(abs(j-yCenter),disty)\n",
    "        if distx**2+disty**2<=radius**2:\n",
    "            return True\n",
    "        return False\n",
    "    # def dist(point1,point2):\n",
    "    #     x1,y1=point1\n",
    "    #     x2,y2=point2\n",
    "    #     return (x1-x2)**2+(y1-y2)**2\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        def f(i: int, j: int, k: int) -> int:\n",
    "            if i <= k <= j:\n",
    "                return 0\n",
    "            return i - k if k < i else k - j\n",
    "\n",
    "        a = f(x1, x2, xCenter)\n",
    "        b = f(y1, y2, yCenter)\n",
    "        return a * a + b * b <= radius * radius\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        def testcr(x,y):\n",
    "            if (x-xCenter)**2+(y-yCenter)**2<=radius**2:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        if testcr(x1,y1) or testcr(x2,y2) or testcr(x1,y2) or testcr(x2,y1):\n",
    "            return True\n",
    "        def testrg(x,y):\n",
    "            if x1<=x<=x2 and y1<=y<=y2:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        if testrg(xCenter+radius,yCenter) or testrg(xCenter-radius,yCenter) or testrg(xCenter,yCenter+radius) or testrg(xCenter,yCenter-radius):\n",
    "            return True\n",
    "        if xCenter-radius<=x1<=x2<=xCenter+radius:\n",
    "            if y1<=yCenter<=y2:\n",
    "                return True\n",
    "        if yCenter-radius<=y1<=y2<=yCenter+radius:\n",
    "            if x1<=xCenter<=x2:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        x = min(abs(xCenter-x1),abs(xCenter-x2)) if xCenter<x1 or xCenter>x2 else 0\n",
    "        y = min(abs(yCenter-y1),abs(yCenter-y2)) if yCenter<y1 or yCenter>y2 else 0\n",
    "        d2 = x**2+y**2\n",
    "        return d2 <= radius**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        distx=float('inf')\n",
    "        disty=float('inf')\n",
    "        for i in range(x1,x2+1):\n",
    "            # if abs(i-xCenter)<distx:\n",
    "            #     xm=i\n",
    "            distx=min(abs(i-xCenter),distx)\n",
    "        for j in range(y1,y2+1):\n",
    "            # if abs(j-yCenter)<disty:\n",
    "            #     ym=j\n",
    "            disty=min(abs(j-yCenter),disty)\n",
    "        if distx**2+disty**2<=radius**2:\n",
    "            return True\n",
    "        return False\n",
    "    # def dist(point1,point2):\n",
    "    #     x1,y1=point1\n",
    "    #     x2,y2=point2\n",
    "    #     return (x1-x2)**2+(y1-y2)**2\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        def f(i: int, j: int, k: int) -> int:\n",
    "            if i <= k <= j:\n",
    "                return 0\n",
    "            return i - k if k < i else k - j\n",
    "\n",
    "        a = f(x1, x2, xCenter)\n",
    "        b = f(y1, y2, yCenter)\n",
    "        return a * a + b * b <= radius * radius"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        x_min = 0\n",
    "        y_min = 0\n",
    "        if x1 > xCenter:\n",
    "            x_min = x1 - xCenter\n",
    "        elif x2 < xCenter:\n",
    "            x_min = xCenter - x2\n",
    "        if y1 > yCenter:\n",
    "            y_min = y1 - yCenter\n",
    "        elif y2 < yCenter:\n",
    "            y_min = yCenter - y2\n",
    "        if pow(x_min, 2) + pow(y_min, 2) <= pow(radius, 2):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        target=radius**2\n",
    "        bian=0\n",
    "        if xCenter<=x2 and xCenter>=x1 and yCenter<=y2 and yCenter>=y1:\n",
    "            return True\n",
    "\n",
    "        for i in range(y1,y2):\n",
    "            x_new=x1 \n",
    "            x_new2=x2\n",
    "            y_new=i\n",
    "            distance=(xCenter-x_new)**2+(yCenter-y_new)**2\n",
    "            distance2=(xCenter-x_new2)**2+(yCenter-y_new)**2\n",
    "            if distance<=target or distance2<=target:\n",
    "                bian=1 \n",
    "                return True\n",
    "        \n",
    "        for j in range(x1,x2):\n",
    "            x_new=j\n",
    "            y_new=y1\n",
    "            y_new2=y2 \n",
    "            distance=(xCenter-x_new)**2+(yCenter-y_new)**2\n",
    "            distance2=(xCenter-x_new)**2+(yCenter-y_new2)**2\n",
    "            if distance<=target or distance2<=target:\n",
    "                bian=1\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, r: int, x: int, y: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        def ran(a,b):\n",
    "            return (a-x)**2 + (b-y)**2 - r**2\n",
    "        if ran(x1,y1) <= 0 or ran(x1,y2) <= 0 or ran(x2,y1) <= 0 or ran(x2,y2) <= 0:\n",
    "            return True\n",
    "        if y1 <= y and y <= y2:\n",
    "            if (x1 <= x-r and x-r <= x2) or (x1 <= x+r and x+r <= x2) or (x1 <= x+r and x-r <= x1):\n",
    "                return True\n",
    "        if x1 <= x and x <= x2:\n",
    "            if (y1 <= y-r and y-r <= y2) or (y1 <= y+r and y+r <= y2) or (y1 <= y+r and y-r <= y1):\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        dx = dy = 0\n",
    "        if yCenter > y2:\n",
    "            dy = yCenter - y2\n",
    "        elif yCenter < y1:\n",
    "            dy = yCenter - y1\n",
    "        if xCenter > x2:\n",
    "            dx = xCenter - x2\n",
    "        elif xCenter < x1:\n",
    "            dx = xCenter - x1\n",
    "        return dx * dx + dy * dy <= radius * radius"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        r = radius ** 2\n",
    "        if x1 <= xCenter <= x2 and y1 <= yCenter <= y2:\n",
    "            return True\n",
    "        elif x1 <= xCenter <= x2 and not (y1 <= yCenter <= y2):\n",
    "            if yCenter < y1:\n",
    "                return y1 - yCenter <= radius\n",
    "            else:\n",
    "                return yCenter - y2 <= radius\n",
    "        elif not (x1 <= xCenter <= x2) and y1 <= yCenter <= y2:\n",
    "            if xCenter < x1:\n",
    "                return x1 - xCenter <= radius\n",
    "            else:\n",
    "                return xCenter - x2 <= radius\n",
    "        elif xCenter < x1 and yCenter < y1:\n",
    "            return (x1 - xCenter) ** 2 + (y1 - yCenter) ** 2 <= r\n",
    "        elif xCenter < x1 and yCenter > y2:\n",
    "            return (x1 - xCenter) ** 2 + (yCenter - y2) ** 2 <= r\n",
    "        elif xCenter > x2 and yCenter < y1:\n",
    "            return (xCenter - x2) ** 2 + (y1 - yCenter) ** 2 <= r\n",
    "        # elif xCenter > x2 and yCenter > y2:\n",
    "        else:\n",
    "            return (xCenter - x2) ** 2 + (yCenter - y2) ** 2 <= r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        if x1 <= xCenter <= x2 and y1 <= yCenter <= y2:\n",
    "            return True\n",
    "        # 条件 2：圆心位于矩形的上下左右四个区域\n",
    "        elif xCenter > x2 and y1 <= yCenter <= y2:# 右\n",
    "            return radius >= xCenter - x2\n",
    "        elif yCenter < y1 and x1 <= xCenter <= x2:# 下\n",
    "            return radius >= y1 - yCenter\n",
    "        elif xCenter < x1 and y1 <= yCenter <= y2:# 左\n",
    "            return radius >= x1 - xCenter\n",
    "        elif yCenter > y2 and x1 <= xCenter <= x2:# 上\n",
    "            return radius >= yCenter - y2\n",
    "        \n",
    "        else:\n",
    "            # 条件 3：判断矩形的四个顶点是否在圆的内部\n",
    "            return min((x1 - xCenter) ** 2 + (y2 - yCenter) ** 2, (x1 - xCenter) ** 2 + (y1 - yCenter) ** 2, (x2 - xCenter) ** 2 + (y2 - yCenter) ** 2, (x2 - xCenter) ** 2 + (y1 - yCenter) ** 2) <= radius ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        def f(i: int, j: int, k: int) -> int:\n",
    "            if i <= k <= j:\n",
    "                return 0\n",
    "            return i - k if k < i else k - j\n",
    "\n",
    "        a = f(x1, x2, xCenter)\n",
    "        b = f(y1, y2, yCenter)\n",
    "        return a * a + b * b <= radius * radius"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        dist = 0\n",
    "        if xCenter < x1 or xCenter > x2:\n",
    "            dist += min((x1 - xCenter) ** 2, (x2 - xCenter) ** 2)\n",
    "        if yCenter < y1 or yCenter > y2:\n",
    "            dist += min((y1 - yCenter) ** 2, (y2 - yCenter) ** 2)\n",
    "        return dist <= radius ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        dist = 0\n",
    "        if xCenter < x1 or xCenter > x2:\n",
    "            dist += min((x1 - xCenter) ** 2, (x2 - xCenter) ** 2)\n",
    "        if yCenter < y1 or yCenter > y2:\n",
    "            dist += min((y1 - yCenter) ** 2, (y2 - yCenter) ** 2)\n",
    "        return dist <= radius ** 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        dx, dy = max(0, x1 - xCenter, xCenter - x2), max(0, y1 - yCenter, yCenter - y2)\n",
    "        return dx ** 2 + dy ** 2 <= radius ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        x, y = (x1+x2)/2, (y1+y2)/2\n",
    "        if xCenter < x:\n",
    "            xCenter = 2*x - xCenter\n",
    "        if yCenter < y:\n",
    "            yCenter = 2*y - yCenter\n",
    "        if xCenter<=x2:\n",
    "            if y<=yCenter<=y2:\n",
    "                return True\n",
    "            else:\n",
    "                return yCenter-y2 <= radius\n",
    "        else:\n",
    "            if yCenter<=y2:\n",
    "                return xCenter-x2 <= radius\n",
    "            else:\n",
    "                distance = sqrt((xCenter-x2)**2+(yCenter-y2)**2)\n",
    "                return distance <= radius"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        if min(0,-(x1-xCenter),(x2-xCenter)) ** 2 + min(0,-(y1-yCenter), (y2-yCenter))** 2<=radius**2: return True\n",
    "        if x1<xCenter and x2>xCenter and y1<yCenter and y2>yCenter:return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        if xCenter >= x1 - radius and xCenter <= x2 + radius and yCenter >= y1 - radius and yCenter <= y2 + radius:\n",
    "            # 左边\n",
    "            if xCenter < x1:\n",
    "                # 左下角\n",
    "                if yCenter < y1:\n",
    "                    # 就是专门写这个if呢\n",
    "                    if (x1-xCenter)**2 + (y1-yCenter)**2 <= radius**2:\n",
    "                        return True\n",
    "                    else:\n",
    "                        return False\n",
    "                # 左上角\n",
    "                if yCenter > y2:\n",
    "                    if (x1-xCenter)**2 + (y2-yCenter)**2 <= radius**2:\n",
    "                        return True\n",
    "                    else:\n",
    "                        return False\n",
    "                return True\n",
    "            elif xCenter > x2:\n",
    "                 # 右下角\n",
    "                if yCenter < y1:\n",
    "                    # 就是专门写这个if呢\n",
    "                    if (x2-xCenter)**2 + (y1-yCenter)**2 <= radius**2:\n",
    "                        return True\n",
    "                    else:\n",
    "                        return False\n",
    "                # 右上角\n",
    "                if yCenter > y2:\n",
    "                    if (x2-xCenter)**2 + (y2-yCenter)**2 <= radius**2:\n",
    "                        return True\n",
    "                    else:\n",
    "                        return False\n",
    "                return True\n",
    "            else:\n",
    "                return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        def f(i: int, j: int, k: int) -> int:\n",
    "            if i <= k <= j:\n",
    "                return 0\n",
    "            return i - k if k < i else k - j\n",
    "\n",
    "        a = f(x1, x2, xCenter)\n",
    "        b = f(y1, y2, yCenter)\n",
    "        return a * a + b * b <= radius * radius\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        def f(i, j, k):\n",
    "            if i <= k <= j:\n",
    "                return 0\n",
    "            return i - k if k < i else k - j\n",
    "\n",
    "        a = f(x1, x2, xCenter)\n",
    "        b = f(y1, y2, yCenter)\n",
    "        return a ** 2 + b ** 2 <= radius ** 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        # 圆心在正方形内的情况先排除\n",
    "        if x1 <= xCenter <= x2 and y1 <= yCenter <= y2:\n",
    "            return True \n",
    "        def check(x,y):\n",
    "            if (x-xCenter)**2 + (y-yCenter)**2 <= radius**2:\n",
    "                return True \n",
    "            return False\n",
    "        # 检查正方形边上的点到圆心的距离\n",
    "        # 上\n",
    "        i = x1 \n",
    "        while i <= x2:\n",
    "            if check(i,y1):\n",
    "                return True\n",
    "            if check(i,y2):\n",
    "                return True\n",
    "            i += 1\n",
    "        i = y1 \n",
    "        while i <= y2:\n",
    "            if check(x1,i):\n",
    "                return True \n",
    "            if check(x2,i):\n",
    "                return True \n",
    "            i += 1\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        def getdis(x1, y1, x2, y2):\n",
    "            return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)\n",
    "        if xCenter + radius < x1:\n",
    "            return False\n",
    "        if xCenter - radius > x2:\n",
    "            return False\n",
    "        if yCenter + radius < y1:\n",
    "            return False\n",
    "        if yCenter - radius > y2:\n",
    "            return False\n",
    "        a = (x1 + x2) / 2\n",
    "        b = (y1 + y2) / 2\n",
    "        if getdis(a, b, xCenter, yCenter) > getdis(x1, y1, x2, y2) / 2 + radius:\n",
    "            return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        dist = 0\n",
    "        if xCenter < x1 or xCenter > x2:\n",
    "            dist += min((x1 - xCenter) ** 2, (x2 - xCenter) ** 2)\n",
    "        if yCenter < y1 or yCenter > y2:\n",
    "            dist += min((y1 - yCenter) ** 2, (y2 - yCenter) ** 2)\n",
    "        return dist <= radius ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        def uclideDist(x, y):\n",
    "            dist = (((xCenter-x)**2) + ((yCenter-y)**2)) ** 0.5\n",
    "            return dist\n",
    "\n",
    "        if xCenter < x1 and yCenter < y1:\n",
    "            if uclideDist(x1, y1) <= radius:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        elif xCenter < x1 and yCenter >= y1 and yCenter <= y2:\n",
    "            if x1 - xCenter <= radius:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        elif xCenter < x1 and yCenter > y2:\n",
    "            if uclideDist(x1,y2) <= radius:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        elif xCenter >= x1 and xCenter <= x2 and yCenter > y2:\n",
    "            if yCenter - y2 <= radius:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        elif xCenter > x2 and yCenter > y2:\n",
    "            if uclideDist(x2,y2) <= radius:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        elif xCenter > x2 and yCenter >= y1 and yCenter <= y2:\n",
    "            if xCenter - x2 <= radius:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        elif xCenter > x2 and yCenter < y1:\n",
    "            if uclideDist(x2,y1) <= radius:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        elif xCenter >= x1 and xCenter <= x2 and yCenter < y1:\n",
    "            if y1 - yCenter <= radius:\n",
    "                return True\n",
    "            else:\n",
    "                return False\n",
    "        elif xCenter >= x1 and xCenter <= x2 and yCenter >= y1 and yCenter <= y2:\n",
    "            return True\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        dist = 0\n",
    "        if xCenter < x1 or xCenter > x2:\n",
    "            dist += min((x1 - xCenter) ** 2, (x2 - xCenter) ** 2)\n",
    "        if yCenter < y1 or yCenter > y2:\n",
    "            dist += min((y1 - yCenter) ** 2, (y2 - yCenter) ** 2)\n",
    "        return dist <= radius ** 2\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        def distance(ux,uy,vx,vy):\n",
    "            return (ux-vx) ** 2 + (uy - vy) ** 2\n",
    "\n",
    "        if x1 <= xCenter <= x2 and y1 <= yCenter <= y2:\n",
    "            return True\n",
    "\n",
    "        if x1 <= xCenter <= x2 and y2 <= yCenter <= y2 + radius:\n",
    "            return True\n",
    "\n",
    "        if x1 <= xCenter <= x2 and y1 - radius <= yCenter <= y1:\n",
    "            return True\n",
    "\n",
    "        if x1 - radius <= xCenter <= x1 and y1 <= yCenter <= y2:\n",
    "            return True\n",
    "\n",
    "        if x2 <= xCenter <= x2 + radius and y1 <= yCenter <= y2:\n",
    "            return True\n",
    "\n",
    "        if distance(xCenter,yCenter,x1,y2) <= radius ** 2:\n",
    "            return True\n",
    "\n",
    "        if distance(xCenter,yCenter,x2,y2) <= radius ** 2:\n",
    "            return True\n",
    "\n",
    "        if distance(xCenter,yCenter,x1,y1) <= radius ** 2:\n",
    "            return True\n",
    "\n",
    "        if distance(xCenter,yCenter,x2,y1) <= radius ** 2:\n",
    "            return True\n",
    "\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        # 考虑圆心和矩形最短的位置，有9种情况\n",
    "        if x1<=xCenter<=x2 and y1<=yCenter<=y2:\n",
    "            return True\n",
    "        if xCenter>x2 and y1<=yCenter<=y2:\n",
    "            return xCenter-x2<=radius\n",
    "        if xCenter<x1 and y1<=yCenter<=y2:\n",
    "            return x1-xCenter<=radius\n",
    "        if x1<=xCenter<=x2 and yCenter>y2:\n",
    "            return yCenter-y2<=radius\n",
    "        if xCenter>x2 and yCenter>y2:\n",
    "            return (xCenter-x2)**2+(yCenter-y2)**2<=radius**2\n",
    "        if xCenter<x1 and yCenter>y2:\n",
    "            return (x1-xCenter)**2+(yCenter-y2)**2<=radius**2\n",
    "        if x1<=xCenter<=x2 and yCenter<y1:\n",
    "            return y1-yCenter<=radius\n",
    "        if xCenter>x2 and yCenter<y1:\n",
    "            return (xCenter-x2)**2+(y1-yCenter)**2<=radius**2\n",
    "        if xCenter<x1 and yCenter<y1:\n",
    "            return (x1-xCenter)**2+(y1-yCenter)**2<=radius**2\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "\n",
    "        if xCenter<x1:\n",
    "            x0 = x1\n",
    "        elif xCenter>x2:\n",
    "            x0 = x2\n",
    "        else:\n",
    "            x0 = xCenter\n",
    "            \n",
    "        if yCenter<y1:\n",
    "            y0 = y1\n",
    "        elif yCenter>y2:\n",
    "            y0 = y2\n",
    "        else:\n",
    "            y0 = yCenter\n",
    "        return (x0-xCenter)**2+(y0-yCenter)**2<=radius**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        x = min((xCenter-x1)**2,(xCenter-x2)**2) if xCenter<x1 or xCenter>x2 else 0\n",
    "        y = min((yCenter-y1)**2,(yCenter-y2)**2) if yCenter<y1 or yCenter>y2 else 0\n",
    "        d2 = x + y\n",
    "        return d2 <= radius**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "\n",
    "        def distance(ux, uy, vx, vy):\n",
    "            return (ux - vx)**2 + (uy - vy)**2\n",
    "\n",
    "        \"\"\"\n",
    "        圆心在矩形内部\n",
    "        \"\"\"\n",
    "        if x1 <= xCenter <= x2 and y1 <= yCenter <= y2:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        圆心在矩形上部\n",
    "        \"\"\"\n",
    "        if x1 <= xCenter <= x2 and y2 <= yCenter <= y2 + radius:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        圆心在矩形下部\n",
    "        \"\"\"\n",
    "        if x1 <= xCenter <= x2 and y1 - radius <= yCenter <= y1:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        圆心在矩形左部\n",
    "        \"\"\"\n",
    "        if x1 - radius <= xCenter <= x1 and y1 <= yCenter <= y2:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        圆心在矩形右部\n",
    "        \"\"\"\n",
    "        if x2 <= xCenter <= x2 + radius and y1 <= yCenter <= y2:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        矩形左上角\n",
    "        \"\"\"\n",
    "        if distance(xCenter, yCenter, x1, y2) <= radius**2:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        矩形左下角\n",
    "        \"\"\"\n",
    "        if distance(xCenter, yCenter, x1, y1) <= radius**2:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        矩形右上角\n",
    "        \"\"\"\n",
    "        if distance(xCenter, yCenter, x2, y2) <= radius**2:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        矩形右下角\n",
    "        \"\"\"\n",
    "        if distance(xCenter, yCenter, x1, y2) <= radius**2:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        无交点\n",
    "        \"\"\"\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        if min(y1,y2) <= yCenter <= max(y1,y2):\n",
    "            if not (xCenter + radius < min(x1,x2) or xCenter - radius > max(x1,x2)):\n",
    "                return True\n",
    "        if min(x1,x2) <= xCenter <= max(x1,x2):\n",
    "            if not (yCenter + radius < min(y1,y2) or yCenter - radius > max(y1,y2)):\n",
    "                return True\n",
    "\n",
    "        if min(x1,x2) <= xCenter <= max(x1,x2) and min(y1,y2) <= yCenter <= max(y1,y2):\n",
    "            return True\n",
    "        def dis(x,y):\n",
    "            return (x-xCenter)**2 + (y-yCenter)**2 < radius**2\n",
    "        if dis(x1,y1) or dis(x1,y2) or dis(x2,y1) or dis(x2,y2):\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        def check(x,y):\n",
    "            return (x-xCenter)**2+(y-yCenter)**2<=radius**2\n",
    "        if x1<=xCenter<=x2 and y1<=yCenter<=y2:\n",
    "            return True\n",
    "        elif x1<=xCenter<=x2:\n",
    "            if yCenter<y1:\n",
    "                return check(xCenter,y1)\n",
    "            else:\n",
    "                return check(xCenter,y2)\n",
    "        elif(y1<=yCenter<=y2):\n",
    "            if xCenter<x1:\n",
    "                return check(x1,yCenter)\n",
    "            else:\n",
    "                return check(x2,yCenter)\n",
    "        else:\n",
    "            if xCenter<x1 and yCenter>y2:\n",
    "                return check(x1,y2)\n",
    "            elif xCenter<x1 and yCenter<y1:\n",
    "                return check(x1,y1)\n",
    "            elif xCenter>x2 and yCenter>y2:\n",
    "                return check(x2,y2)\n",
    "            elif xCenter>x2 and yCenter<y1:\n",
    "                return check(x2,y1)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "\n",
    "        def distance(ux, uy, vx, vy):\n",
    "            return (ux - vx)**2 + (uy - vy)**2\n",
    "\n",
    "        \"\"\"\n",
    "        圆心在矩形内部\n",
    "        \"\"\"\n",
    "        if x1 <= xCenter <= x2 and y1 <= yCenter <= y2:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        圆心在矩形上部\n",
    "        \"\"\"\n",
    "        if x1 <= xCenter <= x2 and y2 <= yCenter <= y2 + radius:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        圆心在矩形下部\n",
    "        \"\"\"\n",
    "        if x1 <= xCenter <= x2 and y1 - radius <= yCenter <= y1:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        圆心在矩形左部\n",
    "        \"\"\"\n",
    "        if x1 - radius <= xCenter <= x1 and y1 <= yCenter <= y2:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        圆心在矩形右部\n",
    "        \"\"\"\n",
    "        if x2 <= xCenter <= x2 + radius and y1 <= yCenter <= y2:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        矩形左上角\n",
    "        \"\"\"\n",
    "        if distance(xCenter, yCenter, x1, y2) <= radius**2:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        矩形左下角\n",
    "        \"\"\"\n",
    "        if distance(xCenter, yCenter, x1, y1) <= radius**2:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        矩形右上角\n",
    "        \"\"\"\n",
    "        if distance(xCenter, yCenter, x2, y2) <= radius**2:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        矩形右下角\n",
    "        \"\"\"\n",
    "        if distance(xCenter, yCenter, x1, y2) <= radius**2:\n",
    "            return True\n",
    "\n",
    "        \"\"\"\n",
    "        无交点\n",
    "        \"\"\"\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        minx = min(abs(x1 - xCenter), abs(x2 - xCenter))\n",
    "        miny = min(abs(y1 - yCenter), abs(y2 - yCenter))\n",
    "        dx = abs((x1 + x2) / 2 - xCenter)\n",
    "        dy = abs((y1 + y2) / 2 - yCenter)\n",
    "        h = (x2 - x1) / 2\n",
    "        v = (y2 - y1) / 2\n",
    "        if dx <= radius + h and y1 <= yCenter <= y2:\n",
    "            return True\n",
    "        elif dy <= radius + v and x1 <= xCenter <= x2:\n",
    "            return True\n",
    "        elif (minx ** 2 + miny **2) <= radius ** 2:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        dis = 0\n",
    "        if xCenter < x1 or xCenter > x2:\n",
    "            dis += min((x1-xCenter)**2,(x2-xCenter)**2)\n",
    "        if yCenter < y1 or yCenter > y2:\n",
    "            dis += min((y1-yCenter)**2,(y2-yCenter)**2)\n",
    "        return dis <= radius**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        x, y = x1, y1\n",
    "        if xCenter > x2:\n",
    "            x = x2\n",
    "        elif xCenter < x1:\n",
    "            x = x1\n",
    "        else:\n",
    "            x = xCenter\n",
    "        if yCenter > y2:\n",
    "            y = y2\n",
    "        elif yCenter < y1:\n",
    "            y = y1\n",
    "        else:\n",
    "            y = yCenter\n",
    "        return (x - xCenter) ** 2 + (y - yCenter) ** 2 <= radius ** 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        if x1 <= xCenter <= x2 and y1 <= yCenter <= y2:\n",
    "            return True\n",
    "        closest1 = (min(x2, max(x1, xCenter)), y1)\n",
    "        closest2 = (min(x2, max(x1, xCenter)), y2)\n",
    "        closest3 = (x1, min(y2, max(y1, yCenter)))\n",
    "        closest4 = (x2, min(y2, max(y1, yCenter)))\n",
    "        return min((x - xCenter) ** 2 + (y - yCenter) ** 2 for x, y in [closest1, closest2, closest3, closest4]) <= radius ** 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        def f(i, j, k):\n",
    "            if i <= k<= j:\n",
    "                return 0\n",
    "            if k<i:\n",
    "                return i-k\n",
    "            if k>j:\n",
    "                return k - j\n",
    "        a = f(x1,x2,xCenter)\n",
    "        b = f(y1, y2, yCenter)\n",
    "        return a*a+b*b<= radius*radius"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        def is_in(x,y,x1,x2,y1,y2):\n",
    "            # 判断 x,y 是否在以x1,y1,x2,y2为左上角和右下角的矩形内\n",
    "            if x1 <= x <= x2 and y1 <= y <= y2:\n",
    "                return True\n",
    "            return False\n",
    "        def is_distance(x,y,x1,y1):\n",
    "            # 求两个点的距离\n",
    "            return (abs(x-x1))**2+(abs(y-y1))**2\n",
    "        # 判断圆心是否在绿色区域\n",
    "        if is_in(xCenter,yCenter,x1,x2,y1,y2):\n",
    "            return True\n",
    "        # 判断圆心是否在蓝色区域\n",
    "        if is_in(xCenter,yCenter,x1,x2,y2,y2+radius) or is_in(xCenter,yCenter,x1,x2,y1-radius,y1) or is_in(xCenter,yCenter,x1-radius,x1,y1,y2) or is_in(xCenter,yCenter,x2,x2+radius,y1,y2):\n",
    "            return True\n",
    "        # 判断是否在红色区域内\n",
    "        if is_distance(xCenter,yCenter,x1,y1) <= radius**2 or is_distance(xCenter,yCenter,x2,y2)<= radius**2 or is_distance(xCenter,yCenter,x2,y1)<= radius**2 or is_distance(xCenter,yCenter,x1,y2)<= radius**2:\n",
    "            return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkOverlap(self, radius: int, xCenter: int, yCenter: int, x1: int, y1: int, x2: int, y2: int) -> bool:\n",
    "        # 方法一\n",
    "        # dis = 0\n",
    "        # if xCenter < x1 or xCenter > x2:\n",
    "        #     dis += min((x1-xCenter)**2,(x2-xCenter)**2)\n",
    "        # if yCenter < y1 or yCenter > y2:\n",
    "        #     dis += min((y1-yCenter)**2,(y2-yCenter)**2)\n",
    "        # return dis <= radius**2\n",
    "        # 方法二\n",
    "        # 判断是否在绿色区域\n",
    "\n",
    "        # 判断是否在蓝色区域\n",
    "\n",
    "        # 判断是否在红色区域\n",
    "        # Helper function to check if a point is inside a rectangle\n",
    "        def isInRectangle(x, y, x1, y1, x2, y2):\n",
    "            return x1 <= x <= x2 and y1 <= y <= y2\n",
    "\n",
    "        # Helper function to calculate the square of the distance between two points\n",
    "        def getDistSquare(x1, y1, x2, y2):\n",
    "            return (x1 - x2) ** 2 + (y1 - y2) ** 2\n",
    "\n",
    "        # Check if the circle's center is inside the rectangle\n",
    "        if isInRectangle(xCenter, yCenter, x1, y1, x2, y2):\n",
    "            return True\n",
    "\n",
    "        # Check if the circle's center is inside the \"blue\" regions\n",
    "        if isInRectangle(xCenter, yCenter, x1 - radius, y1, x1, y2) or \\\n",
    "           isInRectangle(xCenter, yCenter, x1, y2, x2, y2 + radius) or \\\n",
    "           isInRectangle(xCenter, yCenter, x2, y1, x2 + radius, y2) or \\\n",
    "           isInRectangle(xCenter, yCenter, x1, y1 - radius, x2, y1):\n",
    "            return True\n",
    "\n",
    "        # Check if the circle's center is inside the \"red\" regions\n",
    "        if getDistSquare(xCenter, yCenter, x1, y2) <= radius ** 2 or \\\n",
    "           getDistSquare(xCenter, yCenter, x2, y2) <= radius ** 2 or \\\n",
    "           getDistSquare(xCenter, yCenter, x2, y1) <= radius ** 2 or \\\n",
    "           getDistSquare(xCenter, yCenter, x1, y1) <= radius ** 2:\n",
    "            return True\n",
    "\n",
    "        # If none of the conditions are met, there is no overlap\n",
    "        return False\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
